/**
 * https://leetcode.cn/problems/find-minimum-diameter-after-merging-two-trees/submissions/584276692/
 * 3203. 合并两棵树后的最小直径
 * difficulty 陈贝纯 2024.12.01
 * 换根dp
 */

class Solution {
public:
    int ans=0;
    int bfs(int x,vector<vector<int>>& adj){
        queue<int> q;
        q.push(x);
        int n=adj.size();
        vector<bool> vist(n,true);
        ans=0;
        int cur=x;
        vist[cur]=false;
        while(!q.empty()){
            ans++;
            int k=q.size();
            while(k--){
                cur=q.front();
                q.pop();
                for(auto &j:adj[cur]){
                    if(vist[j]){
                        q.push(j);
                        vist[j]=false;
                    }
                }
            }
        }
        return cur;
    }
    int minimumDiameterAfterMerge(vector<vector<int>>& edges1, vector<vector<int>>& edges2) {
        int n1=edges1.size()+1;
        int n2=edges2.size()+1;
        vector<vector<int>> adj1(n1);
        vector<vector<int>> adj2(n2);
        for(auto edges:edges1){
            adj1[edges[0]].push_back(edges[1]);
            adj1[edges[1]].push_back(edges[0]);
        }
        for(auto edges:edges2){
            adj2[edges[0]].push_back(edges[1]);
            adj2[edges[1]].push_back(edges[0]);
        }
        int x1=bfs(0,adj1);
        bfs(x1,adj1);
        int maxlen1=ans-1;
        int x2=bfs(0,adj2);
        bfs(x2,adj2);
        int maxlen2=ans-1;
        int maxlen=max(maxlen1,maxlen2);
        return max(maxlen,(maxlen1+1)/2+(maxlen2+1)/2+1);
    }
};